# -*- coding: utf-8 -*-
# @Author: bao
# @Date:   2017-01-24 10:27:26
# @Last Modified by:   bao
# @Last Modified time: 2017-04-13 09:00:43

import networkx as nx
from datetime import datetime

def k_cycle_network(switch_nums, degree):
    '''
    @ static connected network
    @ cycle graph
    '''
    match_results = {}
    for x in xrange(1, degree+1):
        match = []
        for src in xrange(1, switch_nums+1):
            dst = (src+x-1)%switch_nums + 1 + switch_nums
            match.append((src, dst))
        match_results[x] = match
    return match_results

def k_regular_network(switch_nums, degree, connected = True):
    '''
    Generate k regular graph
    @ degree: dynamic links
    @ return match_results {k:[(src1,dst1),(src2,dst2)]}
    '''
    regular_graph = nx.random_regular_graph(degree, switch_nums) # node id starts from 0
    if connected:
        while not nx.is_connected(regular_graph):
            regular_graph = nx.random_regular_graph(degree, switch_nums)

    bp_src = range (1,switch_nums+1)
    bp_dst = range (switch_nums+1, switch_nums*2+1)

    match_results = bipartite_matchings(regular_graph, bp_src, bp_dst, degree, switch_nums)   
    return match_results

def bipartite_matchings(graph, bp_src, bp_dst, degree, switch_nums):
    '''
    Calculate k matchings
    {k:[(src1,dst1), (src2,dst2), (src3,dst3)...]}
    '''
    starttime = datetime.now()
    # Transform the graph to bipartite graph
    bp_graph = nx.Graph()
    bp_graph.add_nodes_from(bp_src, bipartite=0)
    bp_graph.add_nodes_from(bp_dst, bipartite=1)

    for edge in list(graph.edges()):
        bp_graph.add_edge(edge[0]+1, edge[1]+switch_nums+1)
        bp_graph.add_edge(edge[1]+1, edge[0]+switch_nums+1)

    # Decompose the graph to k matchings
    match_results = {} # port num: matching
    for x in xrange (1, degree+1):
        match = nx.bipartite.maximum_matching(bp_graph)
        #print "match", x, match
        temp_match = []
        for src,dst in match.items():
            if src > switch_nums:
                break
            temp_match.append((src,dst))
            bp_graph.remove_edge(src,dst)
        match_results[x] = temp_match
    endtime = datetime.now()
    timediff = endtime - starttime
    print 'bipartite_matchings %d.' %timediff.seconds,'%ds' %timediff.microseconds
    return match_results